#include "main/utils.h"
using namespace std;

class Solution {
  public:
    int findDuplicate(vector<int>& nums) {
      int len = nums.size();
      int left = 1, right = len - 1, ans = -1;
      while (left <= right) {
        int mid = (left + right ) >> 1;
        int cnt = 0;
        for (auto n : nums) {
          cnt += (n <= mid);
        }
        if (cnt <= mid) {
          left = mid + 1;
        } else {
          right = mid - 1;
          ans = mid;
        }
      }
      return ans;
    }

    int findDuplicate1(vector<int>& nums) {
      int len = nums.size(), ans = 0;
      int bit_max = 31;
      while (!((len - 1) >> bit_max)) {
        --bit_max;
      }
      for (int i = 0; i <= bit_max; ++i) {
        int x = 0, y = 0;
        for (int j = 0; j < len; ++j) {
          if (nums[j] & (1 << i)) {
            ++x;
          }
          if (j >= 1 && (j & (1 << i))) {
            ++y;
          }
        }
        if (x > y) {
          ans |= (1 << i);
        }
      }
      return ans;
    }

    int findDuplicate2(vector<int>& nums) {
      int slow = 0, fast = 0;
      do {
        slow = nums[slow];
        fast = nums[nums[fast]];
      } while (slow != fast);
      slow = 0;
      while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
      }
      return slow;
    }
};

int main() {
  vector<int> input = {1, 3, 4, 2, 2};
  Solution su;
  cout << su.findDuplicate(input) << endl;
  cout << su.findDuplicate1(input) << endl;
  cout << su.findDuplicate2(input) << endl;
}
